package day2;

import java.util.Scanner;
import java.util.*;
import java.io.*;

class Node {
    int x;
    int y;
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Test8 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(1);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int row = in.nextInt();
            int col = in.nextInt();
            int[][] arr = new int[row][col];
            for(int i = 0; i < row; i++) {
                for(int j = 0; j < col; j++) {
                    arr[i][j] = in.nextInt();
                }
            }
            ArrayList<Node> path = new ArrayList<>();
            ArrayList<Node> minPath = new ArrayList<>();
            int[][] book = new int[row][col];
            getMinPath(arr, row, col, 0, 0, book, path, minPath);

            for(Node n : minPath) {
                System.out.println("(" + n.x + "," + n.y + ")");
            }
        }
    }

    //mat: 迷宫矩阵, row, col
    //x, y: 当前位置
    //book: 标记矩阵，标记当前位置是否走过
    //path: 保存当前路径的每一个位置
    //minPath: 保存最短路径
    public static void getMinPath(int[][] mat, int row, int col, int x, int y, int[][] book, ArrayList<Node> path, ArrayList<Node> minPath) {
        // 判断是否越界
        if(x < 0 || y < 0 || x >= row || y >= col || book[x][y] == 1 || mat[x][y] == 1) {
            return;
        }
        // 将当前路径放入 path 中
        path.add(new Node(x, y));
        // 标记当前位置
        book[x][y] = 1;
        // 判断当前位置是否为出口
        if(x == row-1 && y == col-1) {
            // 一条新的路径产生
            // 判断是否是最小
            if(minPath.isEmpty() || path.size() < minPath.size()) {
                minPath.clear();
                for(Node n : path) {
                    minPath.add(n);
                }
            }
        }
        // 继续更新 (x,y) 上下左右的位置
        getMinPath(mat, row, col, x-1, y, book, path, minPath);
        getMinPath(mat, row, col, x+1, y, book, path, minPath);
        getMinPath(mat, row, col, x, y-1, book, path, minPath);
        getMinPath(mat, row, col, x, y+1, book, path, minPath);
        // 把当前位置从路径中移除
        path.remove(path.size()-1);
        book[x][y] = 0;
    }
}

